/*
 * Copyright (C) 2010 Yury Kudryashov.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package name.kudryashov.collections;

import name.kudryashov.base.Argument;
import name.kudryashov.base.Option;
import name.kudryashov.functions.Function;
import name.kudryashov.functions.Function2;
import name.kudryashov.functions.Predicate;
import name.kudryashov.functions.Procedure;
import name.kudryashov.strings.Joiner;

import java.util.*;

import static name.kudryashov.collections.Lists.newArrayList;
import static name.kudryashov.collections.Tuple.tuple;
import static name.kudryashov.functions.Compose.not;

/**
 * Utility operations over {@link java.util.Collection}s.
 */
public final class ExtCollections {

    // TODO count - Count the number of elements in the list which satisfy a predicate
    // TODO diff - Computes the difference between this list and the given list that.
    // TODO drop (n : Int) : List[A]  Returns the list without its n first elements. If this list has less than n elements, the empty list is returned.
    // TODO dropRight (n : Int) : List[A] Returns the list wihout its rightmost n elements.
    // TODO dropWhile (p : (A) => Boolean) : List[A] Returns the longest suffix of this list whose first element does not satisfy the predicate p.
    // TODO indices  Creates a list with all indices in the list. This is equivalent to a call to List.range(0, xs.length).
    // TODO intersect
    // TODO remove Removes all elements of the list which satisfy the predicate p. This is like filter with the predicate inversed.
    // TODO removeDuplicates
    // TODO takeWhile
    // TODO union
    // TODO zipWithIndex  - for lists only

    // prohibit instances
    private ExtCollections() {}

    /**
     * Iterates over the given collection calling the given <code>procedure</code> for each of the
     * collection members.
     * @param c collection, not null
     * @param procedure procedure, not null
     * @param <T> type of the member of the collection
     * @throws NullPointerException any of the arguments is null
     */
    public static <T> void forEach(Collection<T> c, Procedure<? super T> procedure) {
        Argument.requireNotNull(c, "c");
        Argument.requireNotNull(procedure, "procedure");
        for(T t : c) {
            procedure.call(t);
        }
    }

    /**
     * Returns a new collection that contains only those elements from the given collection, for which
     * the given <code>predicate</code> returns true.
     * <p>
     * The returned collections is <b>NOT</b> a live view of the given collection, it is an entirely new collection.
     * To get live view of the filtered collection, use {@link #filterView(java.util.Collection, name.kudryashov.functions.Predicate)}.
     * @param c collection, not null
     * @param predicate predicate, not null
     * @param <T> type of the collection's elements
     * @return a new collection containing only those elements that match the predicate
     * @throws NullPointerException any of the arguments is null
     */
    public static <T> Collection<T> filter(Collection<T> c, Predicate<? super T> predicate) {
        return newArrayList(Iterators.filter(c.iterator(), predicate));
    }

    /**
     * Returns a live view that contains only those elements from the given collection, for which
     * the given <code>predicate</code> returns true. The changes in original collection are reflected in
     * the filtered view and vice versa.
     * <p>
     * The returned collection is not serializable and not thread-safe (although the original one may be).
     * <p>
     * Operations such as {@link java.util.Collection#size()}, {@link java.util.Collection#isEmpty()} etc. iterate
     * over the whole collection so it may be faster to use {@link #filter(java.util.Collection, name.kudryashov.functions.Predicate)}
     * if live view is not required.
     * <p>
     * The resulting collection's iterator does not support {@link java.util.Iterator#remove()}.
     * <p>
     * The {@link java.util.Collection#add(Object)} and {@link java.util.Collection#addAll(java.util.Collection)}
     * methods will throw {@link IllegalArgumentException} if the element(s) to add do not satisfy the
     * <code>predicate</code>
     * <p>
     * Methods such as {@link java.util.Collection#clear()} will remove from original collection only those elements
     * that match the predicate.
     * @param c collection, not null
     * @param predicate predicate, not null
     * @param <T> type of the collection's elements
     * @return a new collection containing only those elements that match the predicate
     * @throws NullPointerException any of the arguments is null
     */
    public static <T> Collection<T> filterView(Collection<T> c, Predicate<? super T> predicate) {
        return new FilteringCollection<T>(c, predicate);
    }

    /**
     * Splits the given collection into two collections - first contains elements for which the given
     * {@code predicate} returns true, second contains elements for which the predicate returns false.
     * <p>
     * The resulting collections are not a "live-view" ones. To get a live view, use {@link #partitionView}.
     * @param c collection to split, not null
     * @param predicate predicate, not null
     * @param <T> type of the elements in the collection
     * @return tuple; first element is a collection of elements that match the predicate, second - that do not
     * match. Any of these two can be empty, but cannot be null.
     * @throws NullPointerException any of the arguments is null
     */
    public static <T> Tuple2<? extends Collection<T>, ? extends Collection<T>> partition(Collection<T> c, Predicate<? super T> predicate) {
        Argument.requireNotNull(c, "c");
        Argument.requireNotNull(predicate, "predicate");
        // We could have used the following:
        // return Tuple.tuple(filter(c, predicate), filter(c, Compose.not(predicate)));
        // but this requires two scans of the collection in addition to creating several temporary objects.
        // So for performance reason we do a little duplication.
        Collection<T> match = new ArrayList<T>();
        Collection<T> notMatch = new ArrayList<T>();
        for(T t : c) {
            if(predicate.apply(t)) {
                match.add(t);
            }
            else {
                notMatch.add(t);
            }
        }
        return tuple(match, notMatch);
    }

    /**
     * Returns two views of the given collection - first contains elements for which the given
     * {@code predicate} returns true, second contains elements for which the predicate returns false.
     * <p>
     * The resulting collections are a "live-view" ones. Changes in these collections are reflected in
     * the original collection and vice versa.
     * <p>
     * The view collections' iterators do not support {@code remove}.
     * <p>
     * The returned collections are not serializable and not thread-safe (although the original one may be).
     * <p>
     * Operations such as {@link java.util.Collection#size()}, {@link java.util.Collection#isEmpty()} etc. iterate
     * over the whole collection so it may be faster to use {@link #partition(java.util.Collection, name.kudryashov.functions.Predicate)}
     * if live view is not required.
     * <p>
     * Methods such as {@link java.util.Collection#clear()} will remove from original collection only those elements
     * that match/do not match the predicate.
     * @param c collection to split, not null
     * @param predicate predicate, not null
     * @param <T> type of the elements in the collection
     * @return tuple; first element is a collection of elements that match the predicate, second - that do not
     * match. Any of these two can be empty, but cannot be null.
     * @throws NullPointerException any of the arguments is null
     */
    public static <T> Tuple2<? extends Collection<T>, ? extends Collection<T>> partitionView(Collection<T> c, Predicate<? super T> predicate) {
        return tuple(filterView(c, predicate), filterView(c, not(predicate)));
    }

    /**
     * Returns true if at least one element satisfying the predicate exists in the collection,
     * false otherwise.
     * <p>
     * Works short-circuited: stops the iteration over the collection when the first matching element is found.
     * @param c collection, not null
     * @param predicate predicate, not null
     * @param <T> element of the collection
     * @return true if at least one element satisfying the predicate exists in the collection,
     * false otherwise.
     * @throws NullPointerException collection is null or collection is not empty and predicate is null
     */
    public static <T> boolean exists(Collection<T> c, Predicate<? super T> predicate) {
        for(T t : c) {
            if(predicate.apply(t)) {
                return true;
            }
        }
        return false;
    }

    /**
     * Checks if all the elements of the given collection satisfy the given predicate.
     * <p>
     * Execution is short-circuited - as soon as a non-matching element is found, iteration stops.
     * @param c collection, not null
     * @param predicate predicate, not null
     * @param <T> element of the collection
     * @return true if all elements of the collection satisfy the predicate, false otherwise.
     * @throws NullPointerException collection is null or collection is not empty and predicate is null
     */
    public static <T> boolean forAll(Collection<T> c, Predicate<? super T> predicate) {
        for(T t : c) {
            if(!predicate.apply(t)) {
                return false;
            }
        }
        return true;
    }

    /**
     * Returns the first occurence of the value in the collection that satisfies the predicate.
     * If no matching element is found, returns null. See {@link #findFirst(java.util.Collection, Object, name.kudryashov.functions.Predicate)}
     * @param c collection, not null
     * @param predicate predicate, not null
     * @param <T> element of the collection
     * @return the first value in the collection that satisfies the given predicate
     * @throws NullPointerException any of the arguments is null
     */
    public static <T> T findFirst(Collection<T> c, Predicate<? super T> predicate) {
        return findFirst(c, null, predicate);
    }

    /**
     * Returns the first occurence of the value in the collection that satisfies the predicate.
     * If no matching element is found, returns the {@code defaultValue}.
     * See also {@link #findFirst(java.util.Collection, name.kudryashov.functions.Predicate)}
     * @param c collection, not null
     * @param defaultValue value to be returned if nothing is found
     * @param predicate predicate, not null
     * @param <T> element of the collection
     * @return the first value in the collection that satisfies the given predicate
     * @throws NullPointerException collection or predicate is null
     */
    public static <T> T findFirst(Collection<T> c, T defaultValue, Predicate<? super T> predicate) {
        Option<T> o = findFirstO(c, predicate);
        return o.isDefined() ? o.get() : defaultValue;
    }

    /**
     * Returns the first occurence of the value in the collection that satisfies the predicate as on
     * {@link name.kudryashov.base.Some} value. If no matching element is found,
     * returns {@link name.kudryashov.base.None}.
     * See also {@link #findFirst(java.util.Collection, name.kudryashov.functions.Predicate)}
     * @param c collection, not null
     * @param predicate predicate, not null
     * @param <T> element of the collection
     * @return the first value in the collection that satisfies the given predicate or
     * {@link name.kudryashov.base.None} if nothing is found
     * @throws NullPointerException collection or predicate is null
     */
    public static <T> Option<T> findFirstO(Collection<T> c, Predicate<? super T> predicate) {
        for(T t : c) {
            if(predicate.apply(t)) {
                return Option.some(t);
            }
        }
        return Option.none();
    }

    /**
     * Returns the last value in the collection that satisfies the predicate.
     * If no matching element is found, returns null. See {@link #findFirst(java.util.Collection, name.kudryashov.functions.Predicate)}
     * <p>
     * Iterates over the whole collection (O(N)), applying predicate to each element. If applying predicate
     * to each element is undesirable, please use <pre>findFirst(reverse(c), predicate}</pre> 
     * @param c collection, not null
     * @param predicate predicate, not null
     * @param <T> element of the collection
     * @return the last value in the collection that satisfies the given predicate or null if nothing is found
     * @throws NullPointerException any of the arguments is null
     */
    public static <T> T findLast(Collection<T> c, Predicate<? super T> predicate) {
        return findLast(c, null, predicate);
    }

    /**
     * Returns the last value in the collection that satisfies the predicate.
     * If no matching element is found, returns {@code defaultValue}.
     * See {@link #findFirst(java.util.Collection, Object, name.kudryashov.functions.Predicate)}
     * <p>
     * Iterates over the whole collection (O(N)), applying predicate to each element. If applying predicate
     * to each element is undesirable, please use <pre>findFirst(reverse(c), defaultValue, predicate}</pre>
     * @param c collection, not null
     * @param defaultValue default value to return
     * @param predicate predicate, not null
     * @param <T> element of the collection
     * @return the last value in the collection that satisfies the given predicate or default value if nothing
     * is found
     * @throws NullPointerException collection or predicate is null
     */
    public static <T> T findLast(Collection<T> c, T defaultValue, Predicate<? super T> predicate) {
        Option<T> o = findLastO(c, predicate);
        return o.isDefined() ? o.get() : defaultValue;
    }

    /**
     * Returns the last value in the collection that satisfies the predicate as {@link name.kudryashov.base.Some}.
     * If no matching element is found, returns {@link name.kudryashov.base.None}.
     * See {@link #findFirstO(java.util.Collection, name.kudryashov.functions.Predicate)}
     * <p>
     * Iterates over the whole collection (O(N)), applying predicate to each element. If applying predicate
     * to each element is undesirable, please use <pre>findFirstO(reverse(c), predicate}</pre>
     * @param c collection, not null
     * @param predicate predicate, not null
     * @param <T> element of the collection
     * @return the last value in the collection that satisfies the given predicate or None if nothing 
     * is found
     * @throws NullPointerException collection or predicate is null
     */
    public static <T> Option<T> findLastO(Collection<T> c, Predicate<? super T> predicate) {
        Argument.requireNotNull(c, "c");
        Argument.requireNotNull(predicate, "predicate");
        boolean found = false;
        T value = null;
        for(T t : c) {
            if(predicate.apply(t)) {
                found = true;
                value = t;
            }
        }
        return found ? Option.some(value) : Option.<T>none();
    }

    /**
     * Maps elements from a given collection to a new collection (which is not a live view of the original one).
     * Mapping is performed applying the given {@code f} to each member of the given collection.
     * <p>
     * Example - converting list of integers to strings:
     * <pre>
     * List&lt;Integer&gt; l = Arrays.asList(1, 2, 3);
     * List&lt;String&gt; s = map(l, new Function&lt;Integer, String&gt;() {
     *     public String apply(Integer arg) {
     *          return String.valueOf(arg);
     *     }
     * }
     * </pre>
     * See also {@link #mapView(java.util.Collection, name.kudryashov.functions.Function)}
     * @param c collection, not null
     * @param f mapping function, not null
     * @param <T> members of collection
     * @param <R> type to which to map
     * @return a new collection containing mappped elements
     * @throws NullPointerException any of the arguments is null
     */
    public static <T, R> Collection<R> map(Collection<T> c, Function<? super T, ? extends R> f) {
        return newArrayList(Iterators.map(c.iterator(), f));
    }

    /**
     * Maps elements from a given collection to a new collection (which is a live view of the original one).
     * Mapping is performed applying the given {@code f} to each member of the given collection.
     * <p>
     * Example - converting list of integers to strings:
     * <pre>
     * List&lt;Integer&gt; l = Arrays.asList(1, 2, 3);
     * List&lt;String&gt; s = mapView(l, new Function&lt;Integer, String&gt;() {
     *     public String apply(Integer arg) {
     *          return String.valueOf(arg);
     *     }
     * }
     * </pre>
     * See also {@link #map(java.util.Collection, name.kudryashov.functions.Function)} 
     * @param c collection, not null
     * @param f mapping function, not null
     * @param <T> members of collection
     * @param <R> type to which to map
     * @return a new collection containing mappped elements, live view of the original
     * @throws NullPointerException any of the arguments is null
     */
    public static <T, R> Collection<R> mapView(Collection<T> c, Function<? super T, ? extends R> f) {
        return new MappingCollection<T, R>(c, f);
    }

    /**
     * Performs a "flatMap" operation for a given collection - i.e. returns a collection containing
     * concatenation of all the collections made by applying the given function to all the collection members.
     * <p>
     * List(List(1,2,3), List(2,3,4)).flatMap(x => x) returns List(1,2,3,2,3,4).
     * @param c collection to perform flatMap on, not null
     * @param f function producing collections to be applied to all {@code c} elements.
     * @param <T> type of the elements in the given collection
     * @param <R> type of the resulting collection
     * @return a new flatmapped collection or empty collection if the function produced empty lists for
     * all collection members
     */
    public static <T, R> Collection<R> flatMap(Collection<T> c, Function<? super T, ? extends Collection<R>> f) {
        Argument.requireNotNull(c, "c");
        Argument.requireNotNull(f, "f");
        List<R> list = new ArrayList<R>();
        for(T t : c) {
            list.addAll(f.apply(t));
        }
        return list;
    }

    /**
     * Performs a left fold of the given collection applying the given function to each element of the
     * collection.
     * @param c collection, not null
     * @param initial initial value
     * @param f folding function, not null
     * @param <R> type of the result
     * @return the folding result or initial value if the list is empty
     * @throws NullPointerException f or c is null
     */
    public static <T, R> R foldLeft(Collection<T> c, R initial, Function2<? super T, R, R> f) {
        return Iterators.foldLeft(c.iterator(), initial, f);
    }

    /**
     * Performs a "right folding" of the collection applying the given function to each element
     * starting from the back of the collection and keeping the function result.
     * <p>
     * {@code initial} value is passed to the first call of the function (with the last element), then the result
     * of the function's call is applied to the {@code last - 1} element etc. The final result is returned
     * from the function.
     * <p>
     * To implement backward iteration this method dumps the collection to array and then
     * calls {@link name.kudryashov.collections.ExtArrays#foldRight(Object[], Object, name.kudryashov.functions.Function2)}
     * <p>
     * If you have a {@link List} it's always faster to use the counterpart method from the {@link Lists} class.
     * This will avoid dumping the collection to array.
     * @param c collection, not null
     * @param initial initial value
     * @param f folding function, not null
     * @param <T> type of element in the collection
     * @param <R> type of the result
     * @return the folding result or the initial value if collection is empty
     * @throws NullPointerException either {@code c} or {@code f} is empty
     */
    @SuppressWarnings({"unchecked"})
    public static <T, R> R foldRight(Collection<T> c, R initial, Function2<? super T, R, R> f) {
        // TODO optimize for RandomAccess lists
        Argument.requireNotNull(c, "c");
        Argument.requireNotNull(f, "f");

        return ExtArrays.foldRight((T[]) c.toArray(), initial, f);
    }

    /**
     * Performs a left reduce on the given collection. 
     * @param c collection, not null, should have elements
     * @param f reducing function, not null
     * @param <T> type of the elements
     * @return the reduced value
     * @throws IllegalArgumentException {@code c} is empty
     * @throws NullPointerException c or f is null
     */
    public static <T> T reduceLeft(Collection<T> c, Function2<? super T, T, T> f) {
        return Iterators.reduceLeft(c.iterator(), f);
    }

    /**
     * Performs a right reduce on the given collection.
     * @param c collection, not null, should have elements
     * @param f reducing function, not null
     * @param <T> type of the elements
     * @return the reduced value
     * @throws IllegalArgumentException {@code c} is empty
     * @throws NullPointerException c or f is null
     */
    public static <T> T reduceRight(Collection<T> c, Function2<? super T, T, T> f) {
        // TODO optimize for RandomAccess lists
        return Iterators.reduceRight(c.iterator(), f);
    }

    /**
     * Reverses the collection. Copies the collection to a new {@link ArrayList} and then calls
     * the {@link java.util.Collections#reverse(java.util.List)} on the given list.
     * Therefore it requires O(N) of memory and O(N) of time.
     * @param c collection to reverse, not null
     * @param <T> type of elements in the collection.
     * @return the reversed collection.
     */
    public static <T> Collection<T> reverse(Collection<T> c) {
        ArrayList<T> list = newArrayList(c);
        Collections.reverse(list);
        return list;
    }

    /**
     * Sorts the given collection producing a sorted copy, keeping the original collection
     * intact. Uses {@link java.util.Collections#sort(java.util.List)} to sort.
     * <p>
     * Sorting is performed according to natural ordering.
     * @param c collection to sort, not null
     * @param <T> type of the elements
     * @return the sorted collection
     * @throws NullPointerException c is null
     */
    public static <T extends Comparable<? super T>> Collection<T> sort(Collection<T> c) {
        List<T> list = newArrayList(c);
        Collections.sort(list);
        return list;
    }

    /**
     * Sorts the given collection producing a sorted copy, keeping the original collection
     * intact. Uses {@link java.util.Collections#sort(java.util.List)} to sort.
     * <p>
     * Sorting is performed according to the given comparator. If the comparator is null, natural ordering
     * is used.
     * @param c collection to sort, not null
     * @param comparator to be used for sorting, not null
     * @param <T> type of the elements
     * @return the sorted collection
     * @throws NullPointerException c or comparator is null
     */
    public static <T> Collection<T> sort(Collection<T> c, Comparator<? super T> comparator) {
        List<T> list = newArrayList(c);
        Collections.sort(list, comparator);
        return list;
    }

    /**
     * Returns an iterator that iterates the collection in the reverse direction (from back to front).
     * <p>
     * Uses {@link #reverse(java.util.Collection)} internally so it requires O(N) of space and O(N) time.
     * @param c collection, not null
     * @param <T> type of elements in the collection.
     * @return the backward iterator
     * @throws NullPointerException collection is null
     */
    public static <T> Iterator<T> backIterator(Collection<T> c) {
        // TODO optimize for RandomAccess lists
        return reverse(c).iterator();
    }

    /**
     * Returns the first element of the given collection
     * @param c collection, not null, not empty
     * @param <T> type of elements
     * @return the first element of the collection
     * @throws IllegalArgumentException collection is empty
     * @throws NullPointerException collection is null
     */
    public static <T> T takeFirst(Collection<T> c) {
        Argument.require(!c.isEmpty(), "c should not be empty");
        if(isRandomAccess(c)) {
            // optimization for RandomAccess lists
            List<T> list = (List<T>) c;
            return list.get(0);
        }
        Iterator<T> it = c.iterator();
        return it.next();
    }

    /**
     * Returns the last element of the given collection. This method works as O(N).
     * @param c collection to take last element from, not null, not empty
     * @param <T> type of elements in the collection
     * @return the last element of the collection
     * @throws IllegalArgumentException collection is empty
     * @throws NullPointerException collections is null
     */
    public static <T> T takeLast(Collection<T> c) {
        Argument.require(!c.isEmpty(), "c should not be empty");
        if(isRandomAccess(c)) {
            // optimization for RandomAccess lists
            List<T> list = (List<T>) c;
            return list.get(list.size() - 1);
        }
        T result;
        Iterator<T> it = c.iterator();
        do {
            result = it.next();
        } while(it.hasNext());
        return result;
    }

    private static <T> boolean isRandomAccess(Collection<T> c) {
        return c instanceof List && c instanceof RandomAccess;
    }

    /**
     * Returns the collection containing {@code count} first elements of the given collection
     * @param c collection, not null
     * @param count count of elements to take. If zero or negative, an empty collection is returned.
     * If it is greater than the size of the collection, the copy of the whole collection is returned.
     * @param <T> type of elements
     * @return the first element of the collection
     * @throws IllegalArgumentException collection is empty
     * @throws NullPointerException collection is null
     */
    public static <T> List<T> takeFirst(Collection<T> c, int count) {
        return newArrayList(Iterators.take(c.iterator(), count));
    }

    /**
     * Returns the collection containing {@code count} last elements of the given collection
     * @param c collection, not null
     * @param count count of elements to take. If zero or negative, an empty collection is returned.
     * If it is greater than the size of the collection, the copy of the whole collection is returned.
     * @param <T> type of elements
     * @return the first element of the collection
     * @throws IllegalArgumentException collection is empty
     * @throws NullPointerException collection is null
     */
    public static <T> List<T> takeLast(Collection<T> c, int count) {
        if(count <= 0) return Collections.emptyList();
        Argument.require(!c.isEmpty(), "c should not be empty");
        if(isRandomAccess(c)) {
            // optimization for RandomAccess lists
            List<T> list = (List<T>) c;
            // copy the sublist
            int size = list.size();
            return newArrayList(list.subList(Math.max(0, size - count), size));
        }
        return newArrayList(Iterators.takeLast(c.iterator(), count));
    }

    /**
     * Returns a string made by concatenating the elements of the given collection with the given separator.
     * <p>
     * ToString() is used for the members of collection.
     * @param c collection, not null
     * @param separator to use for elements concatenation
     * @return string representation of all the collection members, concatenated with the given separator
     * @throws NullPointerException collection is null
     */
    public static <T> String mkString(Collection<T> c, String separator) {
        return Joiner.on(separator).join(c);
    }

    /**
     * Returns a string made by concatenating the elements of the given collection with the given separator.
     * This string is prefixed by the given prefix {@code start} and postfix with the given postfix {@code end}.
     * <p>
     * ToString() is used for the members of collection.
     * <p>
     * <pre>
     * mkString(Arrays.asList(1, 2, 3), "[", ", ", "]") // [1, 2, 3]
     * </pre>
     * @param c collection, not null
     * @param start prefix
     * @param separator to use for elements concatenation
     * @param end postfix
     * @return string representation of all the collection members, concatenated with the given separator
     * @throws NullPointerException collection is null
     */
    public static String mkString(Collection<?> c, String start, String separator, String end) {
        return Joiner.on(separator).join(start, end, c);
    }

    /**
     * Splits the given collection into groups according to the given grouping function.
     * The function takes the element and returns the group to which the element belongs. 
     * @param c collection to split, not null
     * @param f grouping function, not null
     * @param <T> type of elements
     * @param <G> type of groups
     * @return the map of groups to lists of elements in each group. Does not return empty groups. If collection
     * is empty, empty map is returned.
     * @throws NullPointerException collection or function is null is null
     */
    public static <T, G> Map<G, List<T>> group(Collection<T> c, Function<T, G> f) {
        // TODO change to Multimap
        Map<G, List<T>> map = new HashMap<G, List<T>>();
        for(T t : c) {
            G group = f.apply(t);
            if(!map.containsKey(group)) {
                map.put(group, Lists.<T>newArrayList(t));
            }
            else {
                map.get(group).add(t);
            }
        }
        return map;
    }

    /**
     * Splits the given collection into groups according to the given grouping function.
     * The function takes the element and returns the group to which the element belongs, each group
     * is sorted according to the elements' natural ordering.
     * @param c collection to split, not null
     * @param f grouping function, not null
     * @param <T> type of elements
     * @param <G> type of groups
     * @return the map of groups to lists of elements in each group. Does not return empty groups. If collection
     * is empty, empty map is returned.
     * @throws NullPointerException collection or function is null
     */
    public static <T extends Comparable<? super T>, G> Map<G, List<T>> groupAndSortGroups(Collection<T> c, Function<T, G> f) {
        return groupAndSortGroups(c, f, null);
    }

    /**
     * Splits the given collection into groups according to the given grouping function.
     * The function takes the element and returns the group to which the element belongs, each group
     * is sorted according to the given comparator.
     * @param c collection to split, not null
     * @param f grouping function, not null
     * @param comparator comparator to use for sorting, if null then natural sorting is used
     * @param <T> type of elements
     * @param <G> type of groups
     * @return the map of groups to lists of elements in each group. Does not return empty groups. If collection
     * is empty, empty map is returned.
     * @throws NullPointerException collection or function is null
     */
    public static <T, G> Map<G, List<T>> groupAndSortGroups(Collection<T> c, Function<T, G> f, Comparator<? super T> comparator) {
        // TODO change to Multimap
        Map<G, List<T>> map = group(c, f);
        for(Map.Entry<G, List<T>> entry : map.entrySet()) {
            Collections.sort(entry.getValue(), comparator);
        }
        return map;
    }

    /**
     * Returns a slice of the given collection starting from {@code from} index (inclusive) to
     * {@code to} index (exclusive).
     * @param c collection, not null, not empty
     * @param from index from which to slice the collection. Should be equal to or greater than zero.
     * @param to index to which to slice the collection. Should be less than or equal to the size of the collection.
     * If {@code to} is less than {@code from}, an empty collection is returned.
     * @param <T> type of elements in the collection
     * @return the new collection containing all elements of the given collection starting from {@code from} (inclusive)
     * to {@code to} exclusive.
     * @throws NullPointerException collection is null
     */
    public static <T> Collection<T> slice(Collection<T> c, int from,  int to) {
        return newArrayList(Iterators.slice(c.iterator(), from, to));
    }

    /**
     * Returns a slice view of the given collection starting from {@code from} index (inclusive) to
     * {@code to} index (exclusive).
     * <p>
     * The returned collection is a live view of the given collection. {@code size()} of the returned
     * collection is a O(N) operation.
     * @param c collection, not null, not empty
     * @param from index from which to slice the collection. Should be equal to or greater than zero.
     * @param to index to which to slice the collection. Should be less than or equal to the size of the collection.
     * If {@code to} is less than {@code from}, an empty collection is returned.
     * @param <T> type of elements in the collection
     * @return the new collection containing all elements of the given collection starting from {@code from} (inclusive)
     * to {@code to} exclusive.
     * @throws NullPointerException collection is null
     */
    public static <T> Collection<T> sliceView(final Collection<T> c, final int from,  final int to) {
        Argument.requireNotNull(c, "c");
        return new AbstractCollection<T>() {
            public Iterator<T> iterator() {
                return Iterators.slice(c.iterator(), from, to);
            }

            public int size() {
                return Iterators.size(iterator());
            }
        };
    }

    /**
     * Slices a collection into two collections: one contains all the elements up to the first
     * occurrence of the given element identified by equals (inclusive), the other one contains all the rest elements.
     * <p>
     * The returned collections are copies, not views.
     * @param c collection, not null
     * @param element element to slice collection by
     * @param <T>type of elements in the collection
     * @return a tuple, first element is the first part of the collection, second is the rest.
     * @throws NullPointerException the given collection is null
     */
    public static <T> Tuple2<List<T>, List<T>> slice(Collection<T> c, T element) {
        // lord, how many types
        Tuple2<List<T>, List<T>> tuple = Tuple.<List<T>, List<T>>tuple(
                Lists.<T>newArrayList(),
                Lists.<T>newArrayList()
        );
        boolean found = false;
        for(T t : c) {
            if(!found) {
                tuple.get1().add(t);
            }
            else {
                tuple.get2().add(t);
            }
            if((element == null && t == null) || (element != null && element.equals(t))) {
                found = true;
            }
        }
        return tuple;
    }

    /**
     * Returns a collection of pairs composed from the contents of the given collections:
     * members of first collection become a first element of the pair, members of the second collection
     * become the second element of the pair.
     * <p>
     * If the given collections are of different size, the longest is truncated.
     * @param c1 collection to serve as first member of the resulting tuples, not null
     * @param c2 collection to serve as second member of the resulting tuples, not null
     * @param <T1> type of elements in the first collection
     * @param <T2> type of elements in the second collection
     * @return list of tuples produced from the given collections or empty collection if one of the given
     * collections is empty
     * @throws NullPointerException any of the given collections is null
     */
    public static <T1, T2> List<Tuple2<T1, T2>> zip(Collection<? extends T1> c1, Collection<? extends T2> c2) {
        return newArrayList(Iterators.zip(c1.iterator(), c2.iterator()));
    }

    /**
     * Returns a map composed from the contents of the given collections:
     * members of first collection become keys, members of the second collection
     * become values.
     * <p>
     * If the given collections are of different size, the longest is truncated.
     * @param c1 collection to serve as first member of the resulting tuples, not null
     * @param c2 collection to serve as second member of the resulting tuples, not null
     * @param <T1> type of elements in the first collection
     * @param <T2> type of elements in the second collection
     * @return list of tuples produced from the given collections or empty collection if one of the given
     * collections is empty
     * @throws NullPointerException any of the given collections is null
     */
    public static <T1, T2> Map<T1, T2> zipMap(Collection<? extends T1> c1, Collection<? extends T2> c2) {
        return Maps.newHashMap(zip(c1, c2));
    }

    /**
     * Converts the given collection to a set (backed up by a {@link HashSet}). The resulting set
     * is not a view of the given collection, the elements are copied.
     * @param c collection, not null
     * @param <T> type of elements in the collection
     * @return a new set
     */
    public static <T> Set<T> toSet(Collection<T> c) {
        return new HashSet<T>(c);
    }

    /**
     * Returns a new list containing all the elements from the given collection
     * @param c collection, not null
     * @param <T> type of elements
     * @return a new list. If collection is empty, an empty list is returned
     * @throws NullPointerException c is null
     */
    public static <T> List<T> toList(Collection<T> c) {
        return new ArrayList<T>(c);
    }

}
